// Copyright (c) 2012 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "base/test/trace_event_analyzer.h"

#include <math.h>

#include <algorithm>
#include <memory>
#include <set>

#include "base/json/json_reader.h"
#include "base/strings/pattern.h"
#include "base/values.h"

namespace trace_analyzer {

// TraceEvent

TraceEvent::TraceEvent()
    : thread(0, 0)
    , timestamp(0)
    , duration(0)
    , phase(TRACE_EVENT_PHASE_BEGIN)
    , other_event(NULL)
{
}

TraceEvent::TraceEvent(TraceEvent&& other) = default;

TraceEvent::~TraceEvent()
{
}

TraceEvent& TraceEvent::operator=(TraceEvent&& rhs) = default;

bool TraceEvent::SetFromJSON(const base::Value* event_value)
{
    if (event_value->GetType() != base::Value::TYPE_DICTIONARY) {
        LOG(ERROR) << "Value must be TYPE_DICTIONARY";
        return false;
    }
    const base::DictionaryValue* dictionary = static_cast<const base::DictionaryValue*>(event_value);

    std::string phase_str;
    const base::DictionaryValue* args = NULL;

    if (!dictionary->GetString("ph", &phase_str)) {
        LOG(ERROR) << "ph is missing from TraceEvent JSON";
        return false;
    }

    phase = *phase_str.data();

    bool may_have_duration = (phase == TRACE_EVENT_PHASE_COMPLETE);
    bool require_origin = (phase != TRACE_EVENT_PHASE_METADATA);
    bool require_id = (phase == TRACE_EVENT_PHASE_ASYNC_BEGIN || phase == TRACE_EVENT_PHASE_ASYNC_STEP_INTO || phase == TRACE_EVENT_PHASE_ASYNC_STEP_PAST || phase == TRACE_EVENT_PHASE_MEMORY_DUMP || phase == TRACE_EVENT_PHASE_ENTER_CONTEXT || phase == TRACE_EVENT_PHASE_LEAVE_CONTEXT || phase == TRACE_EVENT_PHASE_CREATE_OBJECT || phase == TRACE_EVENT_PHASE_DELETE_OBJECT || phase == TRACE_EVENT_PHASE_SNAPSHOT_OBJECT || phase == TRACE_EVENT_PHASE_ASYNC_END);

    if (require_origin && !dictionary->GetInteger("pid", &thread.process_id)) {
        LOG(ERROR) << "pid is missing from TraceEvent JSON";
        return false;
    }
    if (require_origin && !dictionary->GetInteger("tid", &thread.thread_id)) {
        LOG(ERROR) << "tid is missing from TraceEvent JSON";
        return false;
    }
    if (require_origin && !dictionary->GetDouble("ts", &timestamp)) {
        LOG(ERROR) << "ts is missing from TraceEvent JSON";
        return false;
    }
    if (may_have_duration) {
        dictionary->GetDouble("dur", &duration);
    }
    if (!dictionary->GetString("cat", &category)) {
        LOG(ERROR) << "cat is missing from TraceEvent JSON";
        return false;
    }
    if (!dictionary->GetString("name", &name)) {
        LOG(ERROR) << "name is missing from TraceEvent JSON";
        return false;
    }
    if (!dictionary->GetDictionary("args", &args)) {
        LOG(ERROR) << "args is missing from TraceEvent JSON";
        return false;
    }
    if (require_id && !dictionary->GetString("id", &id)) {
        LOG(ERROR) << "id is missing from ASYNC_BEGIN/ASYNC_END TraceEvent JSON";
        return false;
    }

    // For each argument, copy the type and create a trace_analyzer::TraceValue.
    for (base::DictionaryValue::Iterator it(*args); !it.IsAtEnd();
         it.Advance()) {
        std::string str;
        bool boolean = false;
        int int_num = 0;
        double double_num = 0.0;
        if (it.value().GetAsString(&str)) {
            arg_strings[it.key()] = str;
        } else if (it.value().GetAsInteger(&int_num)) {
            arg_numbers[it.key()] = static_cast<double>(int_num);
        } else if (it.value().GetAsBoolean(&boolean)) {
            arg_numbers[it.key()] = static_cast<double>(boolean ? 1 : 0);
        } else if (it.value().GetAsDouble(&double_num)) {
            arg_numbers[it.key()] = double_num;
        }
        // Record all arguments as values.
        arg_values[it.key()] = it.value().CreateDeepCopy();
    }

    return true;
}

double TraceEvent::GetAbsTimeToOtherEvent() const
{
    return fabs(other_event->timestamp - timestamp);
}

bool TraceEvent::GetArgAsString(const std::string& name,
    std::string* arg) const
{
    const auto it = arg_strings.find(name);
    if (it != arg_strings.end()) {
        *arg = it->second;
        return true;
    }
    return false;
}

bool TraceEvent::GetArgAsNumber(const std::string& name,
    double* arg) const
{
    const auto it = arg_numbers.find(name);
    if (it != arg_numbers.end()) {
        *arg = it->second;
        return true;
    }
    return false;
}

bool TraceEvent::GetArgAsValue(const std::string& name,
    std::unique_ptr<base::Value>* arg) const
{
    const auto it = arg_values.find(name);
    if (it != arg_values.end()) {
        *arg = it->second->CreateDeepCopy();
        return true;
    }
    return false;
}

bool TraceEvent::HasStringArg(const std::string& name) const
{
    return (arg_strings.find(name) != arg_strings.end());
}

bool TraceEvent::HasNumberArg(const std::string& name) const
{
    return (arg_numbers.find(name) != arg_numbers.end());
}

bool TraceEvent::HasArg(const std::string& name) const
{
    return (arg_values.find(name) != arg_values.end());
}

std::string TraceEvent::GetKnownArgAsString(const std::string& name) const
{
    std::string arg_string;
    bool result = GetArgAsString(name, &arg_string);
    DCHECK(result);
    return arg_string;
}

double TraceEvent::GetKnownArgAsDouble(const std::string& name) const
{
    double arg_double = 0;
    bool result = GetArgAsNumber(name, &arg_double);
    DCHECK(result);
    return arg_double;
}

int TraceEvent::GetKnownArgAsInt(const std::string& name) const
{
    double arg_double = 0;
    bool result = GetArgAsNumber(name, &arg_double);
    DCHECK(result);
    return static_cast<int>(arg_double);
}

bool TraceEvent::GetKnownArgAsBool(const std::string& name) const
{
    double arg_double = 0;
    bool result = GetArgAsNumber(name, &arg_double);
    DCHECK(result);
    return (arg_double != 0.0);
}

std::unique_ptr<base::Value> TraceEvent::GetKnownArgAsValue(
    const std::string& name) const
{
    std::unique_ptr<base::Value> arg_value;
    bool result = GetArgAsValue(name, &arg_value);
    DCHECK(result);
    return arg_value;
}

// QueryNode

QueryNode::QueryNode(const Query& query)
    : query_(query)
{
}

QueryNode::~QueryNode()
{
}

// Query

Query::Query(TraceEventMember member)
    : type_(QUERY_EVENT_MEMBER)
    , operator_(OP_INVALID)
    , member_(member)
    , number_(0)
    , is_pattern_(false)
{
}

Query::Query(TraceEventMember member, const std::string& arg_name)
    : type_(QUERY_EVENT_MEMBER)
    , operator_(OP_INVALID)
    , member_(member)
    , number_(0)
    , string_(arg_name)
    , is_pattern_(false)
{
}

Query::Query(const Query& query)
    : type_(query.type_)
    , operator_(query.operator_)
    , left_(query.left_)
    , right_(query.right_)
    , member_(query.member_)
    , number_(query.number_)
    , string_(query.string_)
    , is_pattern_(query.is_pattern_)
{
}

Query::~Query()
{
}

Query Query::String(const std::string& str)
{
    return Query(str);
}

Query Query::Double(double num)
{
    return Query(num);
}

Query Query::Int(int32_t num)
{
    return Query(static_cast<double>(num));
}

Query Query::Uint(uint32_t num)
{
    return Query(static_cast<double>(num));
}

Query Query::Bool(bool boolean)
{
    return Query(boolean ? 1.0 : 0.0);
}

Query Query::Phase(char phase)
{
    return Query(static_cast<double>(phase));
}

Query Query::Pattern(const std::string& pattern)
{
    Query query(pattern);
    query.is_pattern_ = true;
    return query;
}

bool Query::Evaluate(const TraceEvent& event) const
{
    // First check for values that can convert to bool.

    // double is true if != 0:
    double bool_value = 0.0;
    bool is_bool = GetAsDouble(event, &bool_value);
    if (is_bool)
        return (bool_value != 0.0);

    // string is true if it is non-empty:
    std::string str_value;
    bool is_str = GetAsString(event, &str_value);
    if (is_str)
        return !str_value.empty();

    DCHECK_EQ(QUERY_BOOLEAN_OPERATOR, type_)
        << "Invalid query: missing boolean expression";
    DCHECK(left_.get());
    DCHECK(right_.get() || is_unary_operator());

    if (is_comparison_operator()) {
        DCHECK(left().is_value() && right().is_value())
            << "Invalid query: comparison operator used between event member and "
               "value.";
        bool compare_result = false;
        if (CompareAsDouble(event, &compare_result))
            return compare_result;
        if (CompareAsString(event, &compare_result))
            return compare_result;
        return false;
    }
    // It's a logical operator.
    switch (operator_) {
    case OP_AND:
        return left().Evaluate(event) && right().Evaluate(event);
    case OP_OR:
        return left().Evaluate(event) || right().Evaluate(event);
    case OP_NOT:
        return !left().Evaluate(event);
    default:
        NOTREACHED();
        return false;
    }
}

bool Query::CompareAsDouble(const TraceEvent& event, bool* result) const
{
    double lhs, rhs;
    if (!left().GetAsDouble(event, &lhs) || !right().GetAsDouble(event, &rhs))
        return false;
    switch (operator_) {
    case OP_EQ:
        *result = (lhs == rhs);
        return true;
    case OP_NE:
        *result = (lhs != rhs);
        return true;
    case OP_LT:
        *result = (lhs < rhs);
        return true;
    case OP_LE:
        *result = (lhs <= rhs);
        return true;
    case OP_GT:
        *result = (lhs > rhs);
        return true;
    case OP_GE:
        *result = (lhs >= rhs);
        return true;
    default:
        NOTREACHED();
        return false;
    }
}

bool Query::CompareAsString(const TraceEvent& event, bool* result) const
{
    std::string lhs, rhs;
    if (!left().GetAsString(event, &lhs) || !right().GetAsString(event, &rhs))
        return false;
    switch (operator_) {
    case OP_EQ:
        if (right().is_pattern_)
            *result = base::MatchPattern(lhs, rhs);
        else if (left().is_pattern_)
            *result = base::MatchPattern(rhs, lhs);
        else
            *result = (lhs == rhs);
        return true;
    case OP_NE:
        if (right().is_pattern_)
            *result = !base::MatchPattern(lhs, rhs);
        else if (left().is_pattern_)
            *result = !base::MatchPattern(rhs, lhs);
        else
            *result = (lhs != rhs);
        return true;
    case OP_LT:
        *result = (lhs < rhs);
        return true;
    case OP_LE:
        *result = (lhs <= rhs);
        return true;
    case OP_GT:
        *result = (lhs > rhs);
        return true;
    case OP_GE:
        *result = (lhs >= rhs);
        return true;
    default:
        NOTREACHED();
        return false;
    }
}

bool Query::EvaluateArithmeticOperator(const TraceEvent& event,
    double* num) const
{
    DCHECK_EQ(QUERY_ARITHMETIC_OPERATOR, type_);
    DCHECK(left_.get());
    DCHECK(right_.get() || is_unary_operator());

    double lhs = 0, rhs = 0;
    if (!left().GetAsDouble(event, &lhs))
        return false;
    if (!is_unary_operator() && !right().GetAsDouble(event, &rhs))
        return false;

    switch (operator_) {
    case OP_ADD:
        *num = lhs + rhs;
        return true;
    case OP_SUB:
        *num = lhs - rhs;
        return true;
    case OP_MUL:
        *num = lhs * rhs;
        return true;
    case OP_DIV:
        *num = lhs / rhs;
        return true;
    case OP_MOD:
        *num = static_cast<double>(static_cast<int64_t>(lhs) % static_cast<int64_t>(rhs));
        return true;
    case OP_NEGATE:
        *num = -lhs;
        return true;
    default:
        NOTREACHED();
        return false;
    }
}

bool Query::GetAsDouble(const TraceEvent& event, double* num) const
{
    switch (type_) {
    case QUERY_ARITHMETIC_OPERATOR:
        return EvaluateArithmeticOperator(event, num);
    case QUERY_EVENT_MEMBER:
        return GetMemberValueAsDouble(event, num);
    case QUERY_NUMBER:
        *num = number_;
        return true;
    default:
        return false;
    }
}

bool Query::GetAsString(const TraceEvent& event, std::string* str) const
{
    switch (type_) {
    case QUERY_EVENT_MEMBER:
        return GetMemberValueAsString(event, str);
    case QUERY_STRING:
        *str = string_;
        return true;
    default:
        return false;
    }
}

bool Query::GetMemberValueAsDouble(const TraceEvent& event,
    double* num) const
{
    DCHECK_EQ(QUERY_EVENT_MEMBER, type_);

    // This could be a request for a member of |event| or a member of |event|'s
    // associated event. Store the target event in the_event:
    const TraceEvent* the_event = (member_ < OTHER_PID) ? &event : event.other_event;

    // Request for member of associated event, but there is no associated event.
    if (!the_event)
        return false;

    switch (member_) {
    case EVENT_PID:
    case OTHER_PID:
        *num = static_cast<double>(the_event->thread.process_id);
        return true;
    case EVENT_TID:
    case OTHER_TID:
        *num = static_cast<double>(the_event->thread.thread_id);
        return true;
    case EVENT_TIME:
    case OTHER_TIME:
        *num = the_event->timestamp;
        return true;
    case EVENT_DURATION:
        if (!the_event->has_other_event())
            return false;
        *num = the_event->GetAbsTimeToOtherEvent();
        return true;
    case EVENT_COMPLETE_DURATION:
        if (the_event->phase != TRACE_EVENT_PHASE_COMPLETE)
            return false;
        *num = the_event->duration;
        return true;
    case EVENT_PHASE:
    case OTHER_PHASE:
        *num = static_cast<double>(the_event->phase);
        return true;
    case EVENT_HAS_STRING_ARG:
    case OTHER_HAS_STRING_ARG:
        *num = (the_event->HasStringArg(string_) ? 1.0 : 0.0);
        return true;
    case EVENT_HAS_NUMBER_ARG:
    case OTHER_HAS_NUMBER_ARG:
        *num = (the_event->HasNumberArg(string_) ? 1.0 : 0.0);
        return true;
    case EVENT_ARG:
    case OTHER_ARG: {
        // Search for the argument name and return its value if found.
        std::map<std::string, double>::const_iterator num_i = the_event->arg_numbers.find(string_);
        if (num_i == the_event->arg_numbers.end())
            return false;
        *num = num_i->second;
        return true;
    }
    case EVENT_HAS_OTHER:
        // return 1.0 (true) if the other event exists
        *num = event.other_event ? 1.0 : 0.0;
        return true;
    default:
        return false;
    }
}

bool Query::GetMemberValueAsString(const TraceEvent& event,
    std::string* str) const
{
    DCHECK_EQ(QUERY_EVENT_MEMBER, type_);

    // This could be a request for a member of |event| or a member of |event|'s
    // associated event. Store the target event in the_event:
    const TraceEvent* the_event = (member_ < OTHER_PID) ? &event : event.other_event;

    // Request for member of associated event, but there is no associated event.
    if (!the_event)
        return false;

    switch (member_) {
    case EVENT_CATEGORY:
    case OTHER_CATEGORY:
        *str = the_event->category;
        return true;
    case EVENT_NAME:
    case OTHER_NAME:
        *str = the_event->name;
        return true;
    case EVENT_ID:
    case OTHER_ID:
        *str = the_event->id;
        return true;
    case EVENT_ARG:
    case OTHER_ARG: {
        // Search for the argument name and return its value if found.
        std::map<std::string, std::string>::const_iterator str_i = the_event->arg_strings.find(string_);
        if (str_i == the_event->arg_strings.end())
            return false;
        *str = str_i->second;
        return true;
    }
    default:
        return false;
    }
}

Query::Query(const std::string& str)
    : type_(QUERY_STRING)
    , operator_(OP_INVALID)
    , member_(EVENT_INVALID)
    , number_(0)
    , string_(str)
    , is_pattern_(false)
{
}

Query::Query(double num)
    : type_(QUERY_NUMBER)
    , operator_(OP_INVALID)
    , member_(EVENT_INVALID)
    , number_(num)
    , is_pattern_(false)
{
}
const Query& Query::left() const
{
    return left_->query();
}

const Query& Query::right() const
{
    return right_->query();
}

Query Query::operator==(const Query& rhs) const
{
    return Query(*this, rhs, OP_EQ);
}

Query Query::operator!=(const Query& rhs) const
{
    return Query(*this, rhs, OP_NE);
}

Query Query::operator<(const Query& rhs) const
{
    return Query(*this, rhs, OP_LT);
}

Query Query::operator<=(const Query& rhs) const
{
    return Query(*this, rhs, OP_LE);
}

Query Query::operator>(const Query& rhs) const
{
    return Query(*this, rhs, OP_GT);
}

Query Query::operator>=(const Query& rhs) const
{
    return Query(*this, rhs, OP_GE);
}

Query Query::operator&&(const Query& rhs) const
{
    return Query(*this, rhs, OP_AND);
}

Query Query::operator||(const Query& rhs) const
{
    return Query(*this, rhs, OP_OR);
}

Query Query::operator!() const
{
    return Query(*this, OP_NOT);
}

Query Query::operator+(const Query& rhs) const
{
    return Query(*this, rhs, OP_ADD);
}

Query Query::operator-(const Query& rhs) const
{
    return Query(*this, rhs, OP_SUB);
}

Query Query::operator*(const Query& rhs) const
{
    return Query(*this, rhs, OP_MUL);
}

Query Query::operator/(const Query& rhs) const
{
    return Query(*this, rhs, OP_DIV);
}

Query Query::operator%(const Query& rhs) const
{
    return Query(*this, rhs, OP_MOD);
}

Query Query::operator-() const
{
    return Query(*this, OP_NEGATE);
}

Query::Query(const Query& left, const Query& right, Operator binary_op)
    : operator_(binary_op)
    , left_(new QueryNode(left))
    , right_(new QueryNode(right))
    , member_(EVENT_INVALID)
    , number_(0)
{
    type_ = (binary_op < OP_ADD ? QUERY_BOOLEAN_OPERATOR : QUERY_ARITHMETIC_OPERATOR);
}

Query::Query(const Query& left, Operator unary_op)
    : operator_(unary_op)
    , left_(new QueryNode(left))
    , member_(EVENT_INVALID)
    , number_(0)
{
    type_ = (unary_op < OP_ADD ? QUERY_BOOLEAN_OPERATOR : QUERY_ARITHMETIC_OPERATOR);
}

namespace {

    // Search |events| for |query| and add matches to |output|.
    size_t FindMatchingEvents(const std::vector<TraceEvent>& events,
        const Query& query,
        TraceEventVector* output,
        bool ignore_metadata_events)
    {
        for (size_t i = 0; i < events.size(); ++i) {
            if (ignore_metadata_events && events[i].phase == TRACE_EVENT_PHASE_METADATA)
                continue;
            if (query.Evaluate(events[i]))
                output->push_back(&events[i]);
        }
        return output->size();
    }

    bool ParseEventsFromJson(const std::string& json,
        std::vector<TraceEvent>* output)
    {
        std::unique_ptr<base::Value> root = base::JSONReader::Read(json);

        base::ListValue* root_list = NULL;
        if (!root.get() || !root->GetAsList(&root_list))
            return false;

        for (size_t i = 0; i < root_list->GetSize(); ++i) {
            base::Value* item = NULL;
            if (root_list->Get(i, &item)) {
                TraceEvent event;
                if (event.SetFromJSON(item))
                    output->push_back(std::move(event));
                else
                    return false;
            }
        }

        return true;
    }

} // namespace

// TraceAnalyzer

TraceAnalyzer::TraceAnalyzer()
    : ignore_metadata_events_(false)
    , allow_assocation_changes_(true)
{
}

TraceAnalyzer::~TraceAnalyzer()
{
}

// static
TraceAnalyzer* TraceAnalyzer::Create(const std::string& json_events)
{
    std::unique_ptr<TraceAnalyzer> analyzer(new TraceAnalyzer());
    if (analyzer->SetEvents(json_events))
        return analyzer.release();
    return NULL;
}

bool TraceAnalyzer::SetEvents(const std::string& json_events)
{
    raw_events_.clear();
    if (!ParseEventsFromJson(json_events, &raw_events_))
        return false;
    std::stable_sort(raw_events_.begin(), raw_events_.end());
    ParseMetadata();
    return true;
}

void TraceAnalyzer::AssociateBeginEndEvents()
{
    using trace_analyzer::Query;

    Query begin(Query::EventPhaseIs(TRACE_EVENT_PHASE_BEGIN));
    Query end(Query::EventPhaseIs(TRACE_EVENT_PHASE_END));
    Query match(Query::EventName() == Query::OtherName() && Query::EventCategory() == Query::OtherCategory() && Query::EventTid() == Query::OtherTid() && Query::EventPid() == Query::OtherPid());

    AssociateEvents(begin, end, match);
}

void TraceAnalyzer::AssociateAsyncBeginEndEvents()
{
    using trace_analyzer::Query;

    Query begin(
        Query::EventPhaseIs(TRACE_EVENT_PHASE_ASYNC_BEGIN) || Query::EventPhaseIs(TRACE_EVENT_PHASE_ASYNC_STEP_INTO) || Query::EventPhaseIs(TRACE_EVENT_PHASE_ASYNC_STEP_PAST));
    Query end(Query::EventPhaseIs(TRACE_EVENT_PHASE_ASYNC_END) || Query::EventPhaseIs(TRACE_EVENT_PHASE_ASYNC_STEP_INTO) || Query::EventPhaseIs(TRACE_EVENT_PHASE_ASYNC_STEP_PAST));
    Query match(Query::EventName() == Query::OtherName() && Query::EventCategory() == Query::OtherCategory() && Query::EventId() == Query::OtherId());

    AssociateEvents(begin, end, match);
}

void TraceAnalyzer::AssociateEvents(const Query& first,
    const Query& second,
    const Query& match)
{
    DCHECK(allow_assocation_changes_)
        << "AssociateEvents not allowed after FindEvents";

    // Search for matching begin/end event pairs. When a matching end is found,
    // it is associated with the begin event.
    std::vector<TraceEvent*> begin_stack;
    for (size_t event_index = 0; event_index < raw_events_.size();
         ++event_index) {

        TraceEvent& this_event = raw_events_[event_index];

        if (second.Evaluate(this_event)) {
            // Search stack for matching begin, starting from end.
            for (int stack_index = static_cast<int>(begin_stack.size()) - 1;
                 stack_index >= 0; --stack_index) {
                TraceEvent& begin_event = *begin_stack[stack_index];

                // Temporarily set other to test against the match query.
                const TraceEvent* other_backup = begin_event.other_event;
                begin_event.other_event = &this_event;
                if (match.Evaluate(begin_event)) {
                    // Found a matching begin/end pair.
                    // Erase the matching begin event index from the stack.
                    begin_stack.erase(begin_stack.begin() + stack_index);
                    break;
                }

                // Not a match, restore original other and continue.
                begin_event.other_event = other_backup;
            }
        }
        // Even if this_event is a |second| event that has matched an earlier
        // |first| event, it can still also be a |first| event and be associated
        // with a later |second| event.
        if (first.Evaluate(this_event)) {
            begin_stack.push_back(&this_event);
        }
    }
}

void TraceAnalyzer::MergeAssociatedEventArgs()
{
    for (size_t i = 0; i < raw_events_.size(); ++i) {
        // Merge all associated events with the first event.
        const TraceEvent* other = raw_events_[i].other_event;
        // Avoid looping by keeping set of encountered TraceEvents.
        std::set<const TraceEvent*> encounters;
        encounters.insert(&raw_events_[i]);
        while (other && encounters.find(other) == encounters.end()) {
            encounters.insert(other);
            raw_events_[i].arg_numbers.insert(
                other->arg_numbers.begin(),
                other->arg_numbers.end());
            raw_events_[i].arg_strings.insert(
                other->arg_strings.begin(),
                other->arg_strings.end());
            other = other->other_event;
        }
    }
}

size_t TraceAnalyzer::FindEvents(const Query& query, TraceEventVector* output)
{
    allow_assocation_changes_ = false;
    output->clear();
    return FindMatchingEvents(
        raw_events_, query, output, ignore_metadata_events_);
}

const TraceEvent* TraceAnalyzer::FindFirstOf(const Query& query)
{
    TraceEventVector output;
    if (FindEvents(query, &output) > 0)
        return output.front();
    return NULL;
}

const TraceEvent* TraceAnalyzer::FindLastOf(const Query& query)
{
    TraceEventVector output;
    if (FindEvents(query, &output) > 0)
        return output.back();
    return NULL;
}

const std::string& TraceAnalyzer::GetThreadName(
    const TraceEvent::ProcessThreadID& thread)
{
    // If thread is not found, just add and return empty string.
    return thread_names_[thread];
}

void TraceAnalyzer::ParseMetadata()
{
    for (size_t i = 0; i < raw_events_.size(); ++i) {
        TraceEvent& this_event = raw_events_[i];
        // Check for thread name metadata.
        if (this_event.phase != TRACE_EVENT_PHASE_METADATA || this_event.name != "thread_name")
            continue;
        std::map<std::string, std::string>::const_iterator string_it = this_event.arg_strings.find("name");
        if (string_it != this_event.arg_strings.end())
            thread_names_[this_event.thread] = string_it->second;
    }
}

// TraceEventVector utility functions.

bool GetRateStats(const TraceEventVector& events,
    RateStats* stats,
    const RateStatsOptions* options)
{
    DCHECK(stats);
    // Need at least 3 events to calculate rate stats.
    const size_t kMinEvents = 3;
    if (events.size() < kMinEvents) {
        LOG(ERROR) << "Not enough events: " << events.size();
        return false;
    }

    std::vector<double> deltas;
    size_t num_deltas = events.size() - 1;
    for (size_t i = 0; i < num_deltas; ++i) {
        double delta = events.at(i + 1)->timestamp - events.at(i)->timestamp;
        if (delta < 0.0) {
            LOG(ERROR) << "Events are out of order";
            return false;
        }
        deltas.push_back(delta);
    }

    std::sort(deltas.begin(), deltas.end());

    if (options) {
        if (options->trim_min + options->trim_max > events.size() - kMinEvents) {
            LOG(ERROR) << "Attempt to trim too many events";
            return false;
        }
        deltas.erase(deltas.begin(), deltas.begin() + options->trim_min);
        deltas.erase(deltas.end() - options->trim_max, deltas.end());
    }

    num_deltas = deltas.size();
    double delta_sum = 0.0;
    for (size_t i = 0; i < num_deltas; ++i)
        delta_sum += deltas[i];

    stats->min_us = *std::min_element(deltas.begin(), deltas.end());
    stats->max_us = *std::max_element(deltas.begin(), deltas.end());
    stats->mean_us = delta_sum / static_cast<double>(num_deltas);

    double sum_mean_offsets_squared = 0.0;
    for (size_t i = 0; i < num_deltas; ++i) {
        double offset = fabs(deltas[i] - stats->mean_us);
        sum_mean_offsets_squared += offset * offset;
    }
    stats->standard_deviation_us = sqrt(sum_mean_offsets_squared / static_cast<double>(num_deltas - 1));

    return true;
}

bool FindFirstOf(const TraceEventVector& events,
    const Query& query,
    size_t position,
    size_t* return_index)
{
    DCHECK(return_index);
    for (size_t i = position; i < events.size(); ++i) {
        if (query.Evaluate(*events[i])) {
            *return_index = i;
            return true;
        }
    }
    return false;
}

bool FindLastOf(const TraceEventVector& events,
    const Query& query,
    size_t position,
    size_t* return_index)
{
    DCHECK(return_index);
    for (size_t i = std::min(position + 1, events.size()); i != 0; --i) {
        if (query.Evaluate(*events[i - 1])) {
            *return_index = i - 1;
            return true;
        }
    }
    return false;
}

bool FindClosest(const TraceEventVector& events,
    const Query& query,
    size_t position,
    size_t* return_closest,
    size_t* return_second_closest)
{
    DCHECK(return_closest);
    if (events.empty() || position >= events.size())
        return false;
    size_t closest = events.size();
    size_t second_closest = events.size();
    for (size_t i = 0; i < events.size(); ++i) {
        if (!query.Evaluate(*events.at(i)))
            continue;
        if (closest == events.size()) {
            closest = i;
            continue;
        }
        if (fabs(events.at(i)->timestamp - events.at(position)->timestamp) < fabs(events.at(closest)->timestamp - events.at(position)->timestamp)) {
            second_closest = closest;
            closest = i;
        } else if (second_closest == events.size()) {
            second_closest = i;
        }
    }

    if (closest < events.size() && (!return_second_closest || second_closest < events.size())) {
        *return_closest = closest;
        if (return_second_closest)
            *return_second_closest = second_closest;
        return true;
    }

    return false;
}

size_t CountMatches(const TraceEventVector& events,
    const Query& query,
    size_t begin_position,
    size_t end_position)
{
    if (begin_position >= events.size())
        return 0u;
    end_position = (end_position < events.size()) ? end_position : events.size();
    size_t count = 0u;
    for (size_t i = begin_position; i < end_position; ++i) {
        if (query.Evaluate(*events.at(i)))
            ++count;
    }
    return count;
}

} // namespace trace_analyzer
